#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 014. 最长公共前缀.py
@time: 2022/3/2 14:15
@desc: https://leetcode-cn.com/problems/longest-common-prefix/
> 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
    输入：strs = ["flower","flow","flight"]
    输出："fl"
示例 2：
    输入：strs = ["dog","racecar","car"]
    输出：""
    解释：输入不存在公共前缀。

1. Ot(mn), Os(1)

'''
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(str1, str2):
            """
            找到str1, str2的最长公共前缀
            """
            length, idx = min(len(str1), len(str2)), 0
            while idx<length and str1[idx]==str2[idx]:
                idx += 1
            return str1[:idx]

        if not strs:
            return ""
        # 将第一个字符串作为前缀
        prefix, n = strs[0], len(strs)
        for i in range(1, n):
            # 找到当前前缀与遍历到的字符串的前缀
            prefix = lcp(prefix, strs[i])
            # 如果找不到，说明不存在
            if not prefix:
                break
        return prefix